﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Leetcode_Array.Script.StackAndQueue
{
    //栈非常适合做对称匹配类问题。
    //递归的实现就是：每一次递归调用都会把函数的局部变量、参数值和返回地址等压入调用栈，然后递归返回的时候，从栈中弹出上一次递归的各项参数
    //这就是递归为什么可以返回上一层的位置
    class Barackets
    {
        //=========================力扣20 有效的括号
        // 给定一个只包括'(',')','{','}','[',']'的字符串s，判断字符串是否有效
        //有效字符串需满足：
        //1.左括号必须用相同类型的右括号闭合
        //2.左括号必须以正确的顺序闭合
        //思路：括号匹配是使用栈解决的经典问题
        //栈非常适合做对称匹配类问题。
        public bool IsVaild(string s)
        {
            Stack<int> st = new Stack<int>();
            for (int i = 0; i < s.Length; i++)
            {
                //在匹配左括号时，压入右括号，就只需要比较当前元素和栈顶是否一样即可，比压入左括号的代码简单
                if (s[i] == '(')
                    st.Push(')');
                else if (s[i] == '{')
                    st.Push('}');
                else if (s[i] == '[')
                    st.Push(']');
                //遍历过程中，栈已经空了。说明右括号没有找到对应的左括号 return false;
                //遍历过程中，发现栈里没有我们要匹配的字符，所以return false；
                else if (st.Count == 0 || st.Peek() != s[i])
                    return false;
                else
                    st.Pop();//st.peek()==s[i] 栈弹出元素
            }
            //遍历完之后，如果栈不为空，则说明有相应的左括号 没有右括号匹配，所以return false
            //遍历完之后，如果栈为空，则return true;
            return st.Count == 0;
        }


        //======================力扣1047 删除字符串中的所有相邻重复项
        //给出由小写字母组成的字符串s，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
        //在s上反复执行重复项删除操作，知道无法继续删除。
        //在完成所有重复项删除操作后，返回最终的字符串。答案保证唯一
        public string RemoveDuplicates(string s)
        {
            Stack<char> sta = new Stack<char>();
            for(int i = 0;i<s.Length;i++)
            {
                if (sta.Count > 0 && sta.Peek() == s[i])
                {
                    sta.Pop();
                }else
                    sta.Push(s[i]);


            }
            char[] arr = sta.ToArray();
            Array.Reverse(arr);
           
            return new string(arr);
        }
    }
}
